package com.zhugang.week05;

/**
 * @program algorithms
 * @description: nextGreatestLetter
 * @author: chanzhugang
 * @create: 2022/07/11 22:15
 */
public class NextGreatestLetter2 {

    public static void main(String[] args) {
        NextGreatestLetter2 nextGreatestLetter2 = new NextGreatestLetter2();
        char[] letters = new char[]{'c', 'f', 'j' };
        char target = 'd';
        char c = nextGreatestLetter2.nextGreatestLetter(letters, target);
        System.out.println(c);

    }

    /**
     * 744 寻找比目标字母大的最小字母
     *
     * @param letters
     * @param target
     * @return
     */
    public char nextGreatestLetter(char[] letters, char target) {
        // 找第一个大于给定值的元素
        int low = 0;
        int high = letters.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (letters[mid] > target) {
                if (letters[mid - 1] <= target) {
                    return letters[mid];
                } else {
                    high = mid + 1;
                }
            } else {
                low = mid + 1;
            }
        }
        return letters[0];
    }
}